/*
 * TP 1 - IA Miage : Sudoku
 * 
 * @author Solen Quiniou.
 */
import java.util.Stack;
import java.util.Iterator;


public class Sudoku {
	public static int TAILLE = 9;
	public static int count = 0;
	
	public static void main(String[] args) {
		int[][] grille1 = {
					{0,8,0,4,0,2,0,6,0},
					{0,3,4,0,0,0,9,1,0},
					{9,6,0,0,0,0,0,8,4},
					{0,0,0,2,1,6,0,0,0},
					{0,0,0,0,0,0,0,0,0},
					{0,0,0,3,5,7,0,0,0},
					{8,4,0,0,0,0,0,7,5},
					{0,2,6,0,0,0,1,3,0},
					{0,9,0,7,0,1,0,4,0}
				};
		int[][] grille2 = {
			{4,0,2,0,0,0,0,5,0},
			{0,0,3,2,0,0,0,4,9},
			{6,5,0,8,0,0,7,0,3},
			{0,0,8,0,0,7,9,0,0},
			{7,0,0,0,0,0,0,0,2},
			{0,0,9,3,0,0,4,0,0},
			{9,0,5,0,0,2,0,1,4},
			{1,4,0,0,0,3,2,0,0},
			{0,8,0,0,0,0,3,0,6},
		};
		int[][] grille3 = {
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0},
		};
		int[][] grille4 = {
			{7,0,0,0,0,0,0,3,8},
			{6,0,8,0,3,7,0,0,0},
			{0,0,9,0,0,0,4,7,0},
			{0,5,0,2,0,1,0,0,0},
			{0,8,0,0,0,0,0,9,0},
			{0,0,0,5,0,4,0,8,0},
			{0,6,2,0,0,0,8,0,0},
			{0,0,0,3,1,0,2,0,7},
			{8,7,0,0,0,0,0,0,4},
		};
		
		//initialisation
		Grille grilleInit1 = new Grille(TAILLE, grille1);
		grilleInit1.initRestant();
		//initialisation
		Grille grilleInit2 = new Grille(TAILLE, grille2);
		grilleInit2.initRestant();
		//initialisation
		Grille grilleInit3 = new Grille(TAILLE, grille3);
		grilleInit3.initRestant();
		//initialisation
		Grille grilleInit4 = new Grille(TAILLE, grille4);
		grilleInit4.initRestant();
		
		grilleInit4.afficheGrille();
		Stack<Grille> pile = new Stack<Grille>();
		pile.push(grilleInit4);
		
		boolean resul = resoudreSudoku(pile);
		
		
		if(resul){
			System.out.println("La grille a été résolue en "+count+" appels récursifs");
			Grille grilleResul = pile.peek();//pile.firstElement();
			grilleResul.afficheGrille();
		}
		else{
			System.out.println("Aucune solution n'a été trouvée");
			Grille grilleResul = pile.firstElement();
			grilleResul.afficheGrille();
		}
	}//main
	
	/*
	 * Fonction récursive qui recherche la solution, 
	 * en utilisant éventuellement des retours-arriËre.
	 */
	public static boolean resoudreSudoku(Stack<Grille> pileGrilles){
		count++;
		Case c;
		Grille grilleTete = pileGrilles.peek();
		if(grilleTete.getNbCasesVides()==0) {
			return true;
		}
		else {
			c = grilleTete.getCasePossible();
			if(c!=null){
				Iterator it = c.getRestant().iterator();
				Grille copieGrilleTete = new Grille(grilleTete);
				pileGrilles.push(copieGrilleTete);
				grilleTete=pileGrilles.peek();
				
				// 1er cas: On a qu'une possibilité -> Pas d'appel récursif
				while(c.getRestant().size()==1){
					Integer inte = (Integer)it.next();								// Ici c'est un peu bizarre pour récupérer la valeur possible
					int v = inte.intValue();
					grilleTete.setCase(grilleTete.getCase(c.getI(),c.getJ()),v);	// On met la valeur dans la case
					grilleTete.initRestant();										// On propage l'information pour mettre à jour les cases restantes
					//grilleTete.afficheGrille();
					c = grilleTete.getCasePossible();								// On prend une nouvelle case possible
					if(c!=null){
						it = c.getRestant().iterator();
					}
					else {
						return true;												// S'il n'y a plus de case, c'est qu'on a fini
					}

				}
				// 2eme cas: On a plusieurs possibilité -> Appel récursif
				while(it.hasNext()) {
					Integer inte = (Integer)it.next();
					int v = inte.intValue();
					grilleTete.setCase(grilleTete.getCase(c.getI(),c.getJ()),v);
					grilleTete.initRestant();
					//grilleTete.afficheGrille();
					if(resoudreSudoku(pileGrilles)) {
						return true;
					}
				}
			}
		}
		grilleTete.setCase(grilleTete.getCase(c.getI(),c.getJ()),0);
		grilleTete.initRestant();
		pileGrilles.pop();
		return false;
	}//resoudreSudoku

}


